{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.6 Proof of the master theorem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.6-1 $\\star$\n",
    "\n",
    "> Give a simple and exact expression for $n_j$ in equation (4.27) for the case in which b is a positive integer instead of an arbitrary real number."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "n_j=\\left \\lceil \\frac{n}{b^j} \\right \\rceil\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.6-2 $\\star$\n",
    "\n",
    "> Show that if $f(n)=\\Theta(n^{\\log_ba}\\lg^kn)$, where $k \\ge 0$, then the master recurrence has solution $T(n)=\\Theta(n^{\\log_ba}\\lg^{k+1}n)$. For simplicity, confine your analysis to extract powers of $b$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\dots$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.6-3 $\\star$\n",
    "\n",
    "> Show that case 3 of the master theorem is overstated, in the sense that the regularity condition $af(n/b) \\le cf(n)$ for some constant $c < 1$ implies that there exists a constant $\\epsilon > 0$ such that $f(n)=\\Omega(n^{\\log_ba+\\epsilon})$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\dots$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
